package com.cb2.algorithm.leetcode;

/**
 * <a href='https://leetcode.cn/problems/remove-linked-list-elements'>移除链表元素(Remove Linked List Elements)</a>
 * <p>给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。 </p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：head = [1,2,6,3,4,5,6], val = 6
 *      输出：[1,2,3,4,5]
 *
 * 示例 2：
 *      输入：head = [], val = 1
 *      输出：[]
 *
 * 示例 3：
 *      输入：head = [7,7,7,7], val = 7
 *      输出：[]
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>列表中的节点数目在范围 [0, 10^4] 内</li>
 *         <li>1 <= Node.val <= 50</li>
 *         <li>0 <= val <= 50</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/2/7 10:28
 */
public class LC0203RemoveLinkedListElements_S {
    static class Solution {
        public ListNode removeElements(ListNode head, int val) {
            //return removeElementsByIterator(head, val);
            return removeElementsByRecursion(head, val);
        }

        private ListNode removeElementsByIterator(ListNode head, int val) {
            // 给链表添加虚拟头节点，保证头节点能够被删除
            ListNode dummyHead = new ListNode(-1, head);
            ListNode currNode = dummyHead;
            while (currNode.next != null) {
                if (currNode.next.val == val) {
                    currNode.next = currNode.next.next;
                } else {
                    currNode = currNode.next;
                }
            }
            return dummyHead.next;
        }

        private ListNode removeElementsByRecursion(ListNode head, int val) {
            if (head == null) {
                return null;
            }
            // 通过递归，先处理当前节点的后续节点，返回删除节点的头节点，接在当前节点后面
            head.next = removeElementsByRecursion(head.next, val);
            // 处理当前节点
            return head.val == val ? head.next : head;
        }
    }

    public static void main(String[] args) {
        ListNode head1 = new ListNode(1);
        head1.next = new ListNode(2);
        head1.next.next = new ListNode(6);
        head1.next.next.next = new ListNode(3);
        head1.next.next.next.next = new ListNode(4);
        head1.next.next.next.next.next = new ListNode(5);
        head1.next.next.next.next.next.next = new ListNode(6);

        ListNode head2 = new ListNode(7);
        head2.next = new ListNode(7);
        head2.next.next = new ListNode(7);
        head2.next.next.next = new ListNode(7);

        Solution solution = new Solution();
        Printer.printListNode(solution.removeElements(head1, 6));
        Printer.printListNode(solution.removeElements(null, 1));
        Printer.printListNode(solution.removeElements(head2, 7));
    }
}
